//
// Created by mazaiting on 2024/4/29.
//

#include<iostream>
#include<algorithm>

using namespace std;

int BF(string s, string t)            //BF模式匹配算法
{
    int i = 0, j = 0;
    while (i < s.length() && j < t.length()) //两串未遍历完时循环
    {
        if (s[i] == t[j])                //比较的两个字符相同时
        {
            i++;
            j++;
        }                //s和t串依次移到下一个字符
        else                    //比较的两个字符不相同时
        {
            i = i - j + 1;                //i回退到s本趟开始的下一个字符
            j = 0;                    //j移动到t串的开头
        }
    }
    if (j >= t.length()) return i - t.length(); //t串遍历完毕：匹配成功
    else return -1;                //匹配不成功, 返回-1
}

void GetNext(string t, int *next)    //由模式串t求出next值
{
    int j = 0, k = -1;
    next[0] = -1;
    while (j < t.length() - 1) {
        if (k == -1 || t[j] == t[k])    //k为-1或比较的字符相等时
        {
            j++;
            k++;            //依次移到下一个字符
            next[j] = k;
        } else k = next[k];            //比较的字符不相等时k回退
    }
}

int KMP(string s, string t)        //基本KMP算法
{
    int n = s.length(), m = t.length();
    int *next = new int[m];
    GetNext(t, next);            //求出局部匹配信息next数组
    int i = 0, j = 0;
    while (i < n && j < m)            //s和t均没有遍历完
    {
        if (j == -1 || s[i] == t[j])    //j=-1或者比较的字符相同时
        {
            i++;
            j++;                //i,j各增1
        } else j = next[j];            //否则i不变,j回退
    }
    if (j >= m) return i - m;        //t串遍历完毕：匹配成功
    else return -1;            //匹配不成功，返回-1
}

void GetNextval(string t, int *nextval)    //由模式串t求出nextval值
{
    int j = 0, k = -1;
    nextval[0] = -1;
    while (j < t.length()) {
        if (k == -1 || t[j] == t[k])        //k为-1或比较的字符相等时
        {
            j++;
            k++;
            if (t[j] != t[k])            //两个字符不相等时
                nextval[j] = k;
            else
                nextval[j] = nextval[k];
        } else k = nextval[k];            //k回退
    }
}

int KMPval(string s, string t)            //改进的KMP算法
{
    int n = s.length(), m = t.length();
    int *nextval = new int[m];
    GetNextval(t, nextval);            //求出nextval数组
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || s[i] == t[j]) {
            i++;                    //i,j各增1
            j++;
        } else j = nextval[j];            //i不变,j回退
    }
    if (j >= m) return i - m;
    else return -1;
}


int main() {
    string s1 = "", s2, s3 = "Bye";
    s1.append("Good morning");        //s1="Good morning"
    s2 = s1;                //s2="Good morning"
    int i = s2.find("morning");        //i=5
    s2.replace(i, s2.length() - i, s3);    //相当于s2.replace(5,7,s3)
    cout << "s1: " << s1 << endl;
    cout << "s2: " << s2 << endl;
    cout << "s3: " << s3 << endl;
    string s4 = s1;
    reverse(s4.begin(), s4.begin() + 4);    //逆置s4的前面4个字符
    cout << "s4: " << s4 << endl;
    return 0;
}

